package com.linzm.leetcode.primary.exercises3_20230122;

import java.util.Arrays;

/**
 * @Author zimingl
 * @Date 2023/1/25 17:52
 * @Description: 获取生成数组中的最大值
 */
public class Demo24_1646 {
    /**
     * nums[0] = 0
     * nums[1] = 1
     * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
     * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
     * 输入：n = 7
     * 输出：3
     * 解释：根据规则：
     *   nums[0] = 0
     *   nums[1] = 1
     *   nums[(1 * 2) = 2] = nums[1] = 1
     *   nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
     *   nums[(2 * 2) = 4] = nums[2] = 1
     *   nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
     *   nums[(3 * 2) = 6] = nums[3] = 2
     *   nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
     * 因此，nums = [0,1,1,2,1,3,2,3]，最大值 3
     */
    public static void main(String[] args) {
        Demo24_1646 demo24_1646 = new Demo24_1646();
        int n = 7;
        int maximumGenerated = demo24_1646.getMaximumGenerated(n);
        System.out.println(maximumGenerated);
    }

    private int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            int tmp = i / 2;
            if (i % 2 == 0) {
                arr[i] = arr[tmp];
            } else {
                arr[i] = arr[tmp] + arr[tmp + 1];
            }
        }
        Arrays.sort(arr);
        return arr[n];
    }
}
